package datastructure.tree04;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @Filename: TraverseBinaryTree
 * @Author: czh
 * @Data:2023/1/3 11:35
 * 树操作
 */
public class TreeTest {
    public static void main(String[] args) {
        TreeNode a = new TreeNode("x");
//        遍历树
        List<String> result = new ArrayList<>();
        List<String> strings = preOrder(a, result);
        System.out.println(strings.toString());
    }

    /**
     * 前序遍历
     * A B D H K E C F I G J
     * 根左右
     *
     * @param p
     */
    public static List<String> preOrder(TreeNode p, List<String> result) {
        result.add(p.data);
        if (p.lchild != null) {
            preOrder(p.lchild, result);
        }
        if (p.rchild != null) {
            preOrder(p.rchild, result);
        }
        return result;
    }

    /**
     * 中序遍历
     * H K D B E A I F C G J
     * 左根右
     *
     * @param p
     */
    public static void cenOrder(TreeNode p) {
        if (p.lchild != null) {
            cenOrder(p.lchild);
        }
        System.out.print(p.data + " ");
        if (p.rchild != null) {
            cenOrder(p.rchild);
        }
    }

    /**
     * 后序遍历
     * K H D E B I F J G C A
     * 左右根
     *
     * @param p
     */
    public static void postOrder(TreeNode p) {
        if (p.lchild != null) {
            postOrder(p.lchild);
        }
        if (p.rchild != null) {
            postOrder(p.rchild);
        }
        System.out.print(p.data + " ");
    }

    /**
     * 层次遍历
     * A B C D E F G H I J K
     * 从上到下，从左到右 (基于队列实现)
     *
     * @param root
     */
    public static void levelOrder(TreeNode root) {
        Queue q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            TreeNode cur = (TreeNode) q.remove();
            System.out.print(cur.data + " ");
            if (cur.lchild != null) {
                q.add(cur.lchild);
            }
            if (cur.rchild != null) {
                q.add(cur.rchild);
            }
        }
    }
}

/**
 * 树节点
 */
class TreeNode {
    String data;
    TreeNode lchild;
    TreeNode rchild;

    TreeNode(String x) {
        data = x;
    }
}